MIME-Version: 1.0
Server: CERN/3.0
Date: Sunday, 24-Nov-96 22:37:24 GMT
Content-Type: text/html
Content-Length: 5372
Last-Modified: Wednesday, 06-Nov-96 05:01:50 GMT

<HTML>

<HEAD>
<TITLE>CS381/481 Fall 96 Syllabus</TITLE>
</HEAD>

<BODY>

<H1>
CS381/481 Fall 1996<br>
Automata and Computability Theory<br>
Syllabus
</H1>

<HR>

Below is a tentative list of topics to be covered in the course.  They
fall into three major areas:

<ul>
<li><!WA0><!WA0><!WA0><!WA0><a href="#1">Finite Automata and Regular Sets</A>
<li><!WA1><!WA1><!WA1><!WA1><a href="#2">Pushdown Automata and Context Free Languages</A>
<li><!WA2><!WA2><!WA2><!WA2><a href="#3">Turing Machines and Effective Computability</A>
</ul>

Each area will comprise roughly a third of the course.  The entire
body of lecture notes is available in postscript format by clicking <!WA3><!WA3><!WA3><!WA3><a
href="http://www.cs.cornell.edu/Info/Courses/Fall-96/CS481/481.ps">here</A>,
or you can obtain hardcopy for $7 from Linda Mardel in 5147.

<p> The lecture notes are soon to be published as a textbook by
Springer-Verlag.  For that reason, I am very interested in your
comments and suggestions.  In particular, I will pay you $1 for each
mistake, typo, misspelling, etc. that you find that I don't already
know about.  [<!WA4><!WA4><!WA4><!WA4><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/errata.html">known errata</a>]

<p>
Suggested supplementary readings are taken from the text by
J. E. Hopcroft and J. D. Ullman, <i>Introduction to Automata Theory,
Languages, and Computation</i>, Addison-Wesley, 1979 (H&U).

<p> In addition to these specific topics, it is important that by the
end of the course, you have a good general understanding of what it
means for a set to be regular, context-free, recursive, and r.e.; of
the capabilities of finite automata, pushdown automata, and Turing
machines; and of how to describe sets using regular expressions and
context-free grammars.

<hr>

<H2><A NAME = "1">Finite Automata and Regular Sets (H&U Chps. 1-3)</a></H2>

<!WA5><!WA5><!WA5><!WA5><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l1.ps">
Lecture 1:  Course Roadmap and Historical Perspective</a><br>
<!WA6><!WA6><!WA6><!WA6><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l2.ps">
Lecture 2:  Operations on Sets</a><br>
<!WA7><!WA7><!WA7><!WA7><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l3.ps">
Lecture 3:  Finite Automata and Regular Sets</a><br>
<!WA8><!WA8><!WA8><!WA8><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l4.ps">
Lecture 4:  More on Regular Sets</a><br>
<!WA9><!WA9><!WA9><!WA9><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l5.ps">
Lecture 5:  Nondeterministic Finite Automata</a><br>
<!WA10><!WA10><!WA10><!WA10><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l6.ps">
Lecture 6:  The Subset Construction</a><br>
<!WA11><!WA11><!WA11><!WA11><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l7.ps">
Lecture 7:  Pattern Matching and Regular Expressions</a><br>
<!WA12><!WA12><!WA12><!WA12><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l8.ps">
Lecture 8:  More on Pattern Matching</a><br>
<!WA13><!WA13><!WA13><!WA13><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l9.ps">
Lecture 9:  Regular Expressions and Finite Automata</a><br>
<!WA14><!WA14><!WA14><!WA14><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/lA.ps">
Supplementary Lecture A:  Kleene Algebra and Regular Expressions</a><br>
<!WA15><!WA15><!WA15><!WA15><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l10.ps">
Lecture 10:  Homomorphisms</a><br>
<!WA16><!WA16><!WA16><!WA16><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l11.ps">
Lecture 11:  Limitations of Finite Automata</a><br>
<!WA17><!WA17><!WA17><!WA17><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l12.ps">
Lecture 12:  Using the Pumping Lemma</a><br>
<!WA18><!WA18><!WA18><!WA18><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l13.ps">
Lecture 13:  DFA State Minimization</a><br>
<!WA19><!WA19><!WA19><!WA19><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l14.ps">
Lecture 14:  A Minimization Algorithm</a><br>
<!WA20><!WA20><!WA20><!WA20><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l15.ps">
Lecture 15:  Myhill-Nerode Relations</a><br>
<!WA21><!WA21><!WA21><!WA21><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l16.ps">
Lecture 16:  The Myhill-Nerode Theorem</a><br>
<!WA22><!WA22><!WA22><!WA22><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/lB.ps">
Supplementary Lecture B:  Collapsing Nondeterministic Automata</a><br>
<!WA23><!WA23><!WA23><!WA23><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/lC.ps">
Supplementary Lecture C:  Automata on Terms</a><br>
<!WA24><!WA24><!WA24><!WA24><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/lD.ps">
Supplementary Lecture D:  The Myhill-Nerode Theorem for Term Automata</a><br>
<!WA25><!WA25><!WA25><!WA25><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l17.ps">
Lecture 17:  Two-Way Finite Automata</a><br>
<!WA26><!WA26><!WA26><!WA26><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l18.ps">
Lecture 18:  2DFAs and Regular Sets</a><br>

<H2><A NAME = "2">Pushdown Automata and Context Free Languages (H&U Chps. 4-6, 9.1)</H2>

<!WA27><!WA27><!WA27><!WA27><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l19.ps">
Lecture 19:  Context-Free Grammars and Languages</a><br>
<!WA28><!WA28><!WA28><!WA28><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l20.ps">
Lecture 20:  Balanced Parentheses</a><br>
<!WA29><!WA29><!WA29><!WA29><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l21.ps">
Lecture 21:  Normal Forms</a><br>
<!WA30><!WA30><!WA30><!WA30><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l22.ps">
Lecture 22:  The Pumping Lemma for CFLs</a><br>
<!WA31><!WA31><!WA31><!WA31><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l23.ps">
Lecture 23:  Pushdown Automata</a><br>
<!WA32><!WA32><!WA32><!WA32><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/lE.ps">
Supplementary Lecture E:  Final State vs. Empty Stack</a><br>
<!WA33><!WA33><!WA33><!WA33><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l24.ps">
Lecture 24:  PDAs and CFGs</a><br>
<!WA34><!WA34><!WA34><!WA34><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l25.ps">
Lecture 25:  Simulating NPDAs by CFGs</a><br>
<!WA35><!WA35><!WA35><!WA35><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/lF.ps">
Supplementary Lecture F:  Deterministic Pushdown Automata</a><br>
<!WA36><!WA36><!WA36><!WA36><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l26.ps">
Lecture 26:  Parsing</a><br>
<!WA37><!WA37><!WA37><!WA37><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l27.ps">
Lecture 27:  The Cocke-Kasami-Younger Algorithm</a><br>
<!WA38><!WA38><!WA38><!WA38><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/lG.ps">
Supplementary Lecture G:  The Chomsky-Schutzenberger Algorithm</a><br>
<!WA39><!WA39><!WA39><!WA39><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/lH.ps">
Supplementary Lecture H:  Parikh's Theorem</a><br>

<H2><A NAME = "3">Turing Machines and Effective Computability (H&U Chps. 7-8)</H2>

<!WA40><!WA40><!WA40><!WA40><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l28.ps">
Lecture 28:  Turing Machines and Effective Computability</a><br>
<!WA41><!WA41><!WA41><!WA41><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l29.ps">
Lecture 29:  More on Turing Machines</a><br>
<!WA42><!WA42><!WA42><!WA42><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l30.ps">
Lecture 30:  Equivalent Models</a><br>
<!WA43><!WA43><!WA43><!WA43><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l31.ps">
Lecture 31:  Universal Machines and Diagonalization</a><br>
<!WA44><!WA44><!WA44><!WA44><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l32.ps">
Lecture 32:  Decidable and Undecidable Problems</a><br>
<!WA45><!WA45><!WA45><!WA45><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l33.ps">
Lecture 33:  Reductions</a><br>
<!WA46><!WA46><!WA46><!WA46><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l34.ps">
Lecture 34:  Rice's Theorem</a><br>
<!WA47><!WA47><!WA47><!WA47><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l35.ps">
Lecture 35:  Undecidable Problems about CFLs</a><br>
<!WA48><!WA48><!WA48><!WA48><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l36.ps">
Lecture 36:  Other Formalisms</a><br>
<!WA49><!WA49><!WA49><!WA49><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l37.ps">
Lecture 37:  The Lambda-Calculus</a><br>
<!WA50><!WA50><!WA50><!WA50><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/lI.ps">
Supplementary Lecture I:  While Programs</a><br>
<!WA51><!WA51><!WA51><!WA51><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/lJ.ps">
Supplementary Lecture J:  Beyond Undecidability</a><br>
<!WA52><!WA52><!WA52><!WA52><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l38.ps">
Lecture 38:  G&ouml;del's Incompleteness Theorem</a><br>
<!WA53><!WA53><!WA53><!WA53><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l39.ps">
Lecture 39:  Proof of the Incompleteness Theorem</a><br>
<!WA54><!WA54><!WA54><!WA54><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/lK.ps">
Supplementary Lecture K:  G&ouml;del's Proof</a><br>

<hr>
<!WA55><!WA55><!WA55><!WA55><img align=top src="http://www.cs.cornell.edu/Info/Misc/images/hand_point1.gif">
<!WA56><!WA56><!WA56><!WA56><a href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/CS481.html">CS381/481 home page</a>
